ON RELIABILITY OF NON-BRANCHING  PROGRAMS IN A BASIS CONTAINING THE GENERALIZED
CONJUNCTION AT ARBITRARY FAULTS OF COMPUTATIONAL OPERATORS 

Grabovskaya Svetlana Mikhaylovna, Candidate of physical and mathematical sciences, associate professor, subdepartment of computer technologies, Penza State University (40 Krasnaya street, Penza, Russia), ct@pnzgu.ru

519.718

10.21685/2072-3040-2017-3-3

Background. The concept of non-branching programs is closely related to the concept of circuits of functional elements (FE). FE circuits are models of electronic circuits, and non-branching programs (both with conditional stop and without it) model the operation of computing devices. Despite these differences, reliability andcomplexity results obtained for FE circuits are transferred to non-branching programs without stop-operators and vice versa. Prior to the author's work, the problemof constructing reliable (and asymptotically optimal regarding reliability) nonbranchingprograms with a conditional stop-operator has not been considered. Forthe first time this problem was researched for inverse faults at the outputs of computationaloperators, and then for the one-type constant faults at the outputs of computationaloperators. The question of reliability of non-branching programs for faultsof arbitrary type still remains open. In this work the implementation of Booleanfunctions by non-branching programs with a conditional stop-operator is consideredin a complete finite basis containing the generalized conjunction. It is assumed thatthe computational operators are prone to faults of arbitrary type independently ofeach other, and conditional stop-operators are absolutely reliable.
Materials and methods. To raise the reliability of the aource circuits (programs), the iterative approach is used, i.e. multiple duplication of the source circuits (programs). In addition, a new method for constructing non-branching programs hasbeen developed.
Results. The work resulted in discovering an upper bound for the unreliability ofnon-branching programs with a conditional stop-operator in complete finite basis B, containing the generalized conjunction.
Conclusions. If a complete finite basis contains the generalized conjunction, then any Boolean function can be implemented by a non-branching program with a conditional stop-operator of arbitrarily high preassigned reliability.

Boolean function, non-branching program, conditional stopoperator, synthesis, reliability

1. Chashkin A. V. Diskretnyy analiz i issledovanie operatsiy [Discrete analysis and research of operations]. 1997, vol. 4, no. 1, pp. 60–78.
2. Alekhina M. A., Grabovskaya S. M. Russian mathematics. 2012, vol. 56, no. 2,p. 10–18.
3. Yablonskiy S. V. Izbrannye trudy [Selected works]. Moscow: MAKS Press, 2004,584 p.
4. Alekhina M. A., Gusynina Yu. S., Shornikova T. A. Izvestiya vuzov. Matematika [Universityproceedings. Mathematics]. 2017, no. 12, pp. 80–83.
5. Grabovskaya S. M. Problemy avtomatizatsii i upravleniya v tekhnicheskikh sistemakh –2015: cb. st. Mezhdunar. nauch.-tekhn. konf., posvyashchennoy 70-letiyu Pobedy v VelikoyOtechestvennoy voyne (g. Penza, 19–21 maya 2015 g.) [Problems of automationand control in technical systems 2015: proceeding of the International scientific andtechnical conference devoted to the 70th anniversary of the Victory in the Great PatrioticWar (Penza, 19th-21st May 2015)]. Penza: Izd-vo PGU, 2015, pp. 339–342.